题解 CF843B@洛谷 | 843B@Codeforces 【Interactive LowerBound】

有趣的交互题。

题意：有一个递增的单向链表，需要通过询问权值和下一项编号，求出其中 $\ge x$ 的最小元素。

这还不简单？挨个询问一遍就切了嘛（

$n\le 50000$ ，询问最多 $2000$ 次。

~~笑容逐渐凝固。~~

考虑其他方法：

因为已知该链表是递增的，可以先随机询问 $\min(n,1000)-1$ 个点，记录好 $\le x$ 的最大元素以及他下一项的地址。因为询问数远小于 $n$ 的最大可能值，我们将这些询问近似地看做随机的。

经过这些询问后，如果最大元素恰好为 $x$ ，直接输出即可，因为不能得到更小的解了。

否则，我们从下一项的地址开始询问最多 $1000$ 次（因为地址随机，两个被询问的数之间数的个数的期望可以通过除法求得，远小于 $1000$ ），每次移动到获取的 nxt 指针，直到该指针为 $-1$ 或找到 $\ge x$ 的数。对于第二种，因为单调递增的性质，可以知道获取到的是最优解，直接输出；对于第一种，跳出循环后判断最大值与 $x$ 的大小关系，输出该值或者 $-1$ 即可。

注意几点：

经过几次错误，发现这里翻译得很毒瘤，实际上只能进行 $1999$ 次询问（原文如此，经尝试也确实如此），注意不要被坑。
C++ 的 rand() 好像被毒瘤出题人卡掉了，换了几种方式都在第六个点错了，这里可以利用 int 自然溢出手写一个随机。

甚至这个都被卡了：

srand(time(0));
srand(rand()); srand(rand()+19849);

我是用的随机函数可以见代码。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define per(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
#define fil(x,y) memset((x), (y), sizeof(x))
using namespace std;
typedef long long ll;
const int N = 5e4+5, inf = 0x3f3f3f3f;

int n, front, x, ans = -inf, nxt;
vector<int> interact(int _) {
	printf("? %d\n", _);
	fflush(stdout);
	int a, b;
	scanf("%d%d", &a, &b);
	return vector<int>({a, b});
}
void give(int _) {
	printf("! %d\n", _);
	fflush(stdout);
}

int seed, seed2;
void srand(int x, int y) {seed = x; seed2 = y;}
int frand() {return (seed *= 19260817) += ((seed2 += 114514) ^= 1919810);}
int rand() {int res = frand(); while(res <= 0) res += n; return res;}

int main() {
//	srand(time(0));
//	srand(rand()); srand(rand()+19849);
	srand(998244353, 1000000007);
//	rep(i, 1, 100) printf("%d %d %d\n", seed, seed2, rand());
	scanf("%d%d%d", &n, &front, &x);
	nxt = front;
	rep(i, 1, min(n, 1000)-1) {
		int pos = rand() % n + 1;
		vector<int> res = interact(pos);
		if(res[0] <= x && res[0] > ans) nxt = res[1], ans = res[0];
	}
	if(ans == x) return give(x), 0;
	rep(i, 1, 1000) {
		if(nxt == -1) break;
		vector<int> res = interact(nxt);
		if(res[0] >= x) return give(res[0]), 0;
		ans = res[0]; nxt = res[1];
	}
	give(ans>=x?ans:-1);
	return 0;
}